package slidingwindow;

import java.util.Arrays;


public class DoublePointers {

    public static void main(String[] args) {
        DoublePointers doublePointers = new DoublePointers();
        int[] nums = {100000, 100000, 100000, 100000, 100000};
//        System.out.println(doublePointers.fourSum(nums, -2));


    }

    //四数之和
//    public List<List<Integer>> fourSum(int[] nums, int target) {
//        List<List<Integer>> ret = new ArrayList<>();
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length; ) {
//            for (int j = i + 1; j < nums.length; ) {
//                int left = j + 1, right = nums.length - 1;
//                while (left < right) {
//                    long sum = target - nums[i] - nums[j];
//                    if (nums[left] + nums[right] > sum) {
//                        right--;
//                    } else if (nums[left] + nums[right] < sum) {
//                        left++;
//                    } else {
//                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[right], nums[j], nums[i])));
//                        left++;
//                        right--;
//                        while (left < right && nums[left] == nums[left - 1]) {
//                            left++;
//                        }
//                        while (left < right && nums[right] == nums[right + 1]) {
//                            right--;
//                        }
//                    }
//                }
//                j++;
//                while (j < nums.length && nums[j] == nums[j - 1]) {
//                    j++;
//                }
//                i++;
//                while (i < nums.length && nums[i] == nums[i - 1]) {
//                    i++;
//                }
//            }
//
//            return ret;
//        }

        //三数之和
//        public List<List<Integer>> threeSum(int[] nums){
//            List<List<Integer>> ret = new ArrayList<>();
//            Arrays.sort(nums);
//            System.out.println(Arrays.toString(nums));
////        for (int i = 0; i < nums.length;) {
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] > 0) break;
//                int left = i + 1, right = nums.length - 1;
//                while (left < right) {
//                    if (nums[left] + nums[right] < -nums[i]) {
//                        left++;
//                    } else if (nums[left] + nums[right] > -nums[i]) {
//                        right--;
//                    } else {
//                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
//                        left++;
//                        right--;
//                        while (left < right && nums[left] == nums[left - 1]) {
//                            left++;
//                        }
//                        while (left < right && nums[right] == nums[right + 1]) {
//                            right--;
//                        }
//                    }
//
//
//                }
////            i++;
////            while(i < nums.length-1 && nums[i] == nums[i-1]) {
////                i++;
////            }
//                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
//                    i++;
//                }
//            }
//            System.out.println(ret);
//            return ret;
//
//
//        }
//

        //和为 s 的两个数字
        //2.
        public int[] twoSum ( int[] price, int target){
            int left = 0, right = price.length - 1;
            while (left < right) {
                if (price[left] + price[right] > target) {
                    right--;
                } else if (price[left] + price[right] < target) {
                    left++;
                } else {
                    return new int[]{price[left], price[right]};
                }

            }
            return new int[0];
        }

        //1.
        public int[] twoSum1 ( int[] price, int target){
            for (int left = 0; left < price.length; left++) {
                for (int right = left + 1; right < price.length; right++) {
                    if (price[left] + price[right] == target) {
                        return new int[]{price[left], price[right]};
                    }
                }
            }
            return new int[]{0};
        }

        //有效三角形的个数
        public int triangleNumber ( int[] nums){
            int n = nums.length;
            int ret = 0;
            Arrays.sort(nums);
//注意：left 和 right不要定义在for循环外面，因为是要先定义好max值，在定义双指针的
            for (int i = n - 1; i > 1; i--) {
                int right = i - 1, left = 0;
                while (left < right) {
                    if (nums[left] + nums[right] > nums[i]) {
                        ret += right - left;
                        right--;
                    } else {
                        left++;
                    }
                }
            }
            return ret;
        }

        // 盛最多水的容器
        //2.1冲撞指针  4ms
        public int maxArea2 ( int[] height){
            int left = 0, right = height.length - 1;
            int maxV = 0;
            while (left < right) {
                int ret = Math.min(height[left], height[right]) * (right - left);
                maxV = Math.max(ret, maxV);
                if (height[left] > height[right]) {
                    right--;
                } else {
                    left++;
                }

            }
            return maxV;
        }

        //2.2冲撞指针  3ms
        public int maxArea3 ( int[] height){
            int n = height.length;
            int left = 0, right = n - 1;
            int ans = 0;
            while (left < right) {
                int wide = right - left;
                if (height[right] >= height[left]) {
                    ans = Math.max(ans, wide * height[left]);
                    left++;
                } else {
                    ans = Math.max(ans, wide * height[right]);
                    right--;
                }
            }
            return ans;
        }

        //1.暴力解法
        public int maxArea ( int[] height){
            int maxV = 0, ret = 0;

            for (int i = 0; i < height.length; i++) {
                for (int j = height.length - 1; j >= i; j--) {
                    ret = Math.min(height[i], height[j]) * (j - i);
                    if (maxV < ret) {
                        maxV = ret;
                    }
                }
            }
            return maxV;
        }


        //编写一个算法来判断一个数 n 是不是快乐数。
        public static int bitSum ( int n){
            int sum = 0;
            while (n != 0) {
                int t = n % 10;
                sum += t * t;
                n = n / 10;
            }
            return sum;
        }

        public static boolean isHappy ( int n){
            int slow = n, fast = bitSum(n);
            while (slow != fast) {
                slow = bitSum(slow);
                fast = bitSum(bitSum(fast));
            }
//        if(slow == 1) {
//            return true;
//        }
//        return false;
            return slow == 1;
        }

        // 给你⼀个⻓度固定的整数数组arr，请你将该数组中出现的每个零都复写⼀遍，并将其余的元素向右平移。
        //注意：请不要在超过该数组⻓度的位置写⼊元素。请对输⼊的数组就地进⾏上述修改，不要从函数返回任何东西。
        public static void duplicateZeros ( int[] arr){
            int cur = 0, dest = -1, n = arr.length;

            //1.先找到要复写的数
            while (cur < n) {
                if (arr[cur] != 0) {
                    dest++;
                } else {
                    dest += 2;
                }
                if (dest >= n - 1) {
                    break;
                }
                cur++;
            }
            //2.处理边界情况
            if (dest == n) {
                arr[n - 1] = 0;
                dest -= 2;
                cur--;
            }
            //3.从后往前完成复写操作
            while (cur >= 0) {
                if (arr[cur] != 0) {
                    arr[dest] = arr[cur];
                    cur--;
                    dest--;
//               arr[dest--] = arr[cur--];
                } else {
                    arr[dest--] = arr[cur];
                    arr[dest--] = arr[cur];
//               arr[dest--] = 0;
//               arr[dest--] = 0;
                    cur--;

                }
            }

        }

        // 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
        public static void moveZeroes ( int[] nums){
            int temp = 0;
            for (int i = 0, j = -1; i < nums.length; i++) {
                if (nums[i] != 0) {
                    temp = nums[i];
                    nums[i] = nums[++j];
                    nums[j] = temp;

                }
            }
        }
    }
